const BalanceFactor = {
    UNBALANCED_RIGHT: 1,
    SLIGHTLY_UNBALANCED_RIGHT: 2,
    BALANCED: 3,
    SLIGHTLY_UNBALANCED_LEFT: 4,
    UNBALANCED_LEFT: 5
}

function Node(key) {
    this.key = key;
    this.left = null;
    this.right = null;
}

class BinarySearchTree {
    constructor(compareFn = defauleCompare) {
        this.compareFn = compareFn;
        this.root = null;
    }

    insert(key) {
        if (this.root === null) {
            this.root = new Node(key);
        } else {
            this.insertNode(this.root, key);
        }
    }

    insertNode(node, key) {
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if (node.left === null) {
                node.left = new Node(key)
            } else {
                this.insertNode(node.left, key);
            }
        } else {
            if (node.right === null) {
                node.right = new Node(key);
            } else {
                this.insertNode(node.right, key);
            }
        }
    }

    search(key) {
        return this.searchNode(this.root, key);
    }

    searchNode(node, key) {
        if (node === null) {
            return false;
        }
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            return this.searchNode(node.left, key);
        } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
            return this.searchNode(node.right, key);
        } else {
            return true;
        }
    }

    // 中序遍历
    inOrderTraverse(callback) {
        this.inOrderTraverseNode(this.root, callback)
    }

    inOrderTraverseNode(node, callback) {
        if (node !== null) {
            this.inOrderTraverseNode( node.left, callback);
            callback(node.key);
            this.inOrderTraverseNode(node.right, callback);
        }
    }

    // 先序遍历
    preOrderTraverse(callback) {
        this.preOrderTraverseNode(this.root, callback);
    }

    preOrderTraverseNode(node, callback) {
        if (node !== null) {
            callback(node.key);
            this.preOrderTraverseNode(node.left, callback);
            this.preOrderTraverseNode(node.right, callback);
        }
    }

    // 后序遍历
    postOrderTraverse(callback) {
        this.postOrderTraverseNode(this.root, callback);
    }

    postOrderTraverseNode(node, callback) {
        if (node !== null) {
            this.postOrderTraverseNode(node.left, callback);
            this.postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }

    min() {
        return this.minNode(this.root);
    }

    minNode(node) {
        let current = node;
        while(current !== null && current.left !== null) {
            current = current.left;
        }
        return current;
    }

    max() {
        return this.maxNode(this.root)
    }

    maxNode(node) {
        let current = node;
        while(current !== null && current.right !== null) {
            current = current.right;
        }
        return current;
    }

    remove(key) {
        this.root = this.removeNode(this.root, key);
    }

    removeNode(node, key) {
        if (node === null) {
            return null;
        }
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (this.compareFn(key. node.key) === Compare.BIGGER_THAN) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            // key === node.key
            // 情况1
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }
            // 情况2
            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }
            // 情况3
            const aux = this.minNode(node.right); // 找到继承者
            node.key = aux.key; // 找到之后更新值
            node.right = this.removeNode(node.right, aux.key); // 移除下层中key = aux.key的那个节点
            return node;
        }
    }
}


// Adelson-Velskii-Landi树 (AVL树)
class AVLTree extends BinarySearchTree {
    constructor(compareFn = defauleCompare) {
        super(compareFn);
        this.compareFn = compareFn;
        this.root = null;
    }

    getNodeHeight(node) {
        if (node === null) {
            return -1;
        }
        return Math.max(
            this.getNodeHeight(node.left),
            this.getNodeHeight(node.right)
        ) + 1;
    }

    getBalanceFactor(node) {
        const heightDiff = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
        switch (heightDiff) {
            case -2:
                return BalanceFactor.UNBALANCED_RIGHT;
            case -1:
                return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
            case 1:
                return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
            case 2:
                return BalanceFactor.UNBALANCED_LEFT;
            default:
                return BalanceFactor.BALANCED;
        }
    }

    // L-L 向右的单旋转

    rotationLL (node) {
        const tmp = node.left;
        node.left = tmp.left;
        tmp.right = node;
        return tmp;
    }

    // R-R 向左的单旋转

    rotationRR (node) {
        const tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        return tmp;
    }

    // L-R 向右的双旋转 (先LL后RR)

    rotationLR (node) {
        node.left = this.rotationRR(node.left);
        return this.rotationLL(node);
    }

    // R-L 向左的双旋转 (先RR后LL)

    rotationRL(node) {
        node.right = this.rotationLL(node.right);
        return this.rotationRR(node);
    }

    insert(key) {
        this.root = this.insertNode(this.root, key);
    }

    insertNode(node, key) {
        if (node === null) {
            return new Node(key);
        } else if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            node.left = this.insertNode(node.left, key);
        } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
            node.right = this.insertNode(node.right, key);
        } else {
            return node;
        }

        const balanceFactor = this.getBalanceFactor(node); // 计算平衡因子
        if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) { // 插入左侧子节点之后不平衡了
            if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
                node = this.rotationLL(node);
            } else {
                return this.rotationLR(node);
            }
        }
        if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
            if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
                node = this.rotationRR(node);
            } else {
                return this.rotationRL(node);
            }
        }
        return node;
    }

    removeNode() {
        // ...
    }
}

// 红黑树的规则
// 1. 所有节点 不是黑的就是红的
// 2. 根节点是黑的
// 3. 所有的叶子节点都是黑的 (用null引用表示的节点)
// 4. 如果有一个节点是红的，那它2个子节点都是黑的
// 5. 不能有2个相邻的红节点，一个红节点不能有红的父节点或子节点
// 6. 从给定的节点到它的后代节点(null/叶子节点)的所有路径包含数量相同的黑色节点。

class RedBlackNode extends Node {
    constructor(key) {
        super(key);
        this.key = key;
        this.color = Colors.RED;
        this.parent = null;
    }

    isRed() {
        return this.color === Colors.RED;
    }
}

class RedBlackTree extends BinarySearchTree {
    constructor(compareFn = defauleCompare) {
        super(compareFn);
        this.compareFn = compareFn;
        this.root = null;
    }

    rotationLL(node) {
        const tmp = node.left;
        node.left = tmp.right;
        if (tmp.right && tmp.right.key) {
            tmp.right.parent = node;
        }
        tmp.parent = node.parent;
        if (!node.parent) {
            this.root = tmp;
        }
        else {
            if (node === node.parent.left) {
                node.parent.left = tmp;
            } else {
                node.parent.right = tmp;
            }
        }
        tmp.right = node;
        node.parent = tmp;
    }

    rotationRR(node) {
        const tmp = node.right;
        node.right = tmp.left;
        if (tmp.left && tmp.left.key) {
            tmp.left.parent = node;
        }
        tmp.parent = node.parent;
        if (!node.parent) {
            this.root = tmp;
        }
        else {
            if (node === node.parent.left) {
                node.parent.left = tmp;
            } else {
                node.parent.right = tmp;
            }
        }
        tmp.left = node;
        node.parent = tmp;
    }

    insert(key) {
        if (this.root === null) {
            this.root = new RedBlackNode(key);
            this.root.color = Colors.BLACK
        } else {
            const newNode = this.insertNode(this.root, key);
            this.fixTreeProperties(newNode);
        }
    }

    insertNode(node, key) {
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if (node.left === null) {
                node.left = new RedBlackNode(key);
                node.left.parent = node;
                return node.left;
            } else {
                return this.insertNode(node.left, key);
            }
        } else if (node.right === null) {
            node.right = new RedBlackNode(key);
            node.right.parent = node;
            return node.right;
        } else {
            return this.insertNode(node.right, key);
        }
    }

    fixTreeProperties(node) {
        while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK) {
            let parent = node.parent;
            const grandParent = parent.parent;
            // A.父节点是左侧子节点
            if (grandParent && grandParent.left === parent) {
                const uncle = grandParent.right;
                // 1A 叔节点也是红色的 -- 需要重新填色
                if (uncle && uncle.color === Colors.RED) {
                    grandParent.color = Colors.RED;
                    parent.color = Colors.BLACK;
                    uncle.color = Colors.BLACK;
                    node = grandParent;
                } else {
                    // 2A 节点是右侧子节点 - 左旋转
                    if (node === parent.right) {
                        this.rotationRR(parent)
                        node = parent;
                        parent = node.parent;
                    }
                    // 3A 节点是左侧子节点 - 右旋转
                    this.rotationLL(grandParent);
                    parent.color = Colors.BLACK;
                    grandParent.color = Colors.RED;
                    grandParent.color = Colors.RED;
                    node = parent;
                }
            } else {
                // B. 父节点是右侧子节点
                const uncle = grandParent.left;
                // 1B 叔节点也是红色的 -- 需要重新填色
                if (uncle && uncle.color === Colors.RED) {
                    grandParent.color = Colors.RED;
                    parent.color = Colors.BLACK;
                    uncle.color = Colors.BLACK;
                    node = grandParent;
                } else {
                    // 2B 节点是左侧子节点 - 左旋转
                    if (node === parent.left) {
                        this.rotationLL(parent);
                        node = parent;
                        parent = node.parent;
                    }
                    // 3B 节点是右侧子节点 - 右旋转
                    this.rotationRR(grandParent);
                    parent.color = Colors.BLACK;
                    grandParent.color = Colors.BLACK;
                    node = parent;
                }
            }
        }
        this.root.color = Colors.BLACK;
    }
}